package HashTable;

import java.util.HashMap;
import java.util.Map;

public class _748_ShortestCompletingWord {
    //hint:first,change the licenseplate into lowercase and ignore digits,second,
    //loop every word and check if it comtains all the letters in licenseplates,if that,
    //check if it's length is shortest and occur in the first place
    public String shortestCompletingWord(String licensePlate, String[] words) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (Character c : licensePlate.toCharArray()) {
            if (Character.isLetter(c)) {
                c = Character.toLowerCase(c);
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                } else {
                    map.put(c, 1);
                }
            }
        }
        String shortestWord = "aaaaaaaaaaaaaaaa";
        for (String s : words) {
            Map<Character, Integer> tempMap = new HashMap<>();
            for (Character c : s.toCharArray()) {
                if (tempMap.containsKey(c)) {
                    tempMap.put(c, tempMap.get(c) + 1);
                } else {
                    tempMap.put(c, 1);
                }
            }
            boolean satisfy = true;
            for (Map.Entry<Character, Integer> m : map.entrySet()) {
                if (tempMap.containsKey(m.getKey())) {
                    if (m.getValue() > tempMap.get(m.getKey())) {
                        satisfy = false;
                        break;
                    }
                }else{
                    satisfy = false;
                    break;
                }
            }
            if (satisfy &&s.length()<shortestWord.length()) {
                shortestWord =  s;
            }
        }
        return shortestWord;
    }
}
